package q2157_groupStrings;

import CommonClass.UF;

import java.util.*;

public class Solution {
    public int[] groupStrings(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int num = 0;
            // 先把每一个word转换成一个26位的数字 也就是压缩
            for (int j = 0; j < word.length(); j++) {
                num += (1 << (word.charAt(j) - 'a'));
            }
            // 注意 题目中是不考虑字母顺序的 所以对于 ab 和 ba 转化后两个应该是属于同一个字符串
            // 因此map中对于同类字符串会加一
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        // 通过分类 map的key形成了一个list 它的大小也就是并查集的大小
        List<Integer> list = new ArrayList<>(map.keySet());
        // 根据二进制中1的数量做一个排序
        list.sort(Comparator.comparingInt(Integer::bitCount));
        UF union = new UF(list.size());
        // 唯一的问题在于：构建并查集的时候，有的字符串簇它的大小一开始并不是1（类似于ab和ba会被归类到一起）
        // 此时就要操作union的size
        for (int i = 0; i < list.size(); i++) {
            int v = map.get(list.get(i));
            union.size[i] = v;
        }
        // 接下来就是union的过程了
        for (int i = 0; i < list.size(); i++) {
            int n1 = list.get(i);
            int c1 = Integer.bitCount(n1);
            for (int j = 1 + i; j < list.size(); j++) {
                int n2 = list.get(j);
                int c2 = Integer.bitCount(n2);
                // 如果两个bitCount大于1 代表至少有两个字符的差 不符合条件
                if (c2 - c1 > 1) {
                    break;
                }

                if (union.isConnected(i, j)) {
                    continue;
                }
                // 相等的时候代表 可能是 abc 和 adc 这样的情况
                // 所以需要以下条件
                // s1与s2的长度相同，结果按位为1的数量大于等于len(s1)-1
                // s1与s2长度相差为1，结果按位为1的数量等于Math.min(len(s1),len(s2))
                if (c1 == c2) {
                    if (Integer.bitCount(n1 & n2) < c1 - 1) {
                        continue;
                    }
                } else {
                    if (Integer.bitCount(n1 & n2) < c1) {
                        continue;
                    }
                }
                union.union(i, j);
            }
        }
        return new int[]{union.count(), union.getMaxConnectSize()};
    }
}

